package com.berchen.offer;

import java.util.LinkedList;
import java.util.Queue;

/**
 *给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
 *               1
 *           2        2
 *        3    4   4    3
 *
 *
 *  第一次：根节点的左右节点进行比较
 *  第二次  根节点左子结点的左子结点 和根节点的右子节点的右子节点进行比较
 *  第三次 根节点的左子结点的右子节点 和根节点的右子节点和左子节点进行比较
 *
 *  通过队列来实现
 */
public class Test10 {
    boolean isSymmetrical(TreeNode pRoot) {

        if (pRoot == null){
            return true;
        }
        Queue<TreeNode> deque = new LinkedList<>();
        // 根节点的左右节点进行比较
        deque.offer(pRoot.left);
        deque.offer(pRoot.right);
        while (!deque.isEmpty()) {
            TreeNode leftNode = deque.poll();
            TreeNode rightNode = deque.poll();
            if (leftNode == null && rightNode == null) {
                continue;
            }
            // 只要一个不满足就直接弹出去  该树就不是对称二叉树了
            if (leftNode == null || rightNode == null || leftNode.val != rightNode.val) {
                return false;
            }
            // 两两进行比较
            deque.offer(leftNode.left); // 左子节点的左子节点
            deque.offer(rightNode.right);   // 右子节点的右子节点

            // 两两进行比较
            deque.offer(leftNode.right);    // 左子结点的右子节点
            deque.offer(rightNode.left);    // 右子节点的左子结点
        }
        return true;

    }
}
